package mySort;
//归并排序
public class MergeSort {
    //两组两组之间归并
    private void merge(int[] arr, int left, int mid, int right) {
        //创建一个临时数组
        int[] tmpArr = new int[right - left + 1];
        int index = 0;

        int start1 = left;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = right;
        //这里就可以取等于号了，如果只有一个元素也要处理
        while (start1 <= end1 && start2 <= end2) {
            if (arr[start1] <= arr[start2]) {
                tmpArr[index++] = arr[start1++];
            } else {
                tmpArr[index++] = arr[start2++];
            }
        }
        while (start1 <= end1) {
            tmpArr[index++] = arr[start1++];
        }
        while (start2 <= end2) {
            tmpArr[index++] = arr[start2++];
        }

        //两个分散区间合并以后再整合到原数组上面去
        for (int i = 0; i < index; i++) {
            arr[i + left] = tmpArr[i];
        }
    }

    private void helper(int[] arr, int left, int right) {
        if (left >= right) {
            return ;
        }
        int mid = left + ((right - left) >>> 1); //先分
        helper(arr, left, mid);
        helper(arr, mid + 1, right);

        merge(arr, left, mid, right); //合并两组数组
    }

    public void mergeSort(int[] arr) {
        helper(arr, 0, arr.length - 1);
    }
}
